/*
 * @lc app=leetcode.cn id=352 lang=cpp
 *
 * [352] 将数据流变为多个不相交区间
 */

// @lc code=start
const long long INF = 1e18;

class SummaryRanges {
public:
    //利用底层为红黑树的set数据结构
    //存储区间
    //利用upper_bound找到第一个不包含x的区间

    set<pair<long long, long long>> S;

    /** Initialize your data structure here. */
    SummaryRanges() {
        //哨兵
        S.insert({-INF, -INF});
        S.insert({INF, INF});
    }
    
    void addNum(int val) {
        auto r = S.upper_bound({val, INF});
        auto l = r;
        l--;

        //r是第一个不包含val的区间
        //l是上一个区间

        if(val <= l->second)
            return;
        else if (l->second == val - 1 && r->first == val + 1){
            S.insert({l->first, r->second});
            S.erase(l);
            S.erase(r);
        }
        else if (l->second == val - 1){
            S.insert({l->first, val});
            S.erase(l);
        }
        else if (r->first == val + 1){
            S.insert({val, r->second});
            S.erase(r);
        }
        else S.insert({val, val});

        return;
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        for(auto [x, y] : S){
            if(x != -INF && x != INF)
                ans.push_back({int(x),int(y)});
        }
        return ans;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */
// @lc code=end

